package com.leetcode.algorithm.y22.m07.w3;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 49. 字母异位词分组
 * 
 * https://leetcode.cn/problems/group-anagrams/
 * 
 * @author jie.deng
 *
 */
class Question0049Solution01 {

	public List<List<String>> groupAnagrams(String[] strs) {
		List<List<String>> retList = new ArrayList<>();
		int len = strs.length;
		if (len == 0) {
			return retList;
		}
		List<String> list = new ArrayList<>();
		list.add(strs[0]);
		if (len == 1) {
			retList.add(list);
			return retList;
		}

		int[][] cntArr = new int[len][26];
		for (int i = 0; i < len; i++) {
			String str = strs[i];
			for (int j = 0; j < str.length(); j++) {
				cntArr[i][str.charAt(j) - 'a']++;
			}
		}

		Map<Integer, List<String>> map = new HashMap<>();
		map.put(0, list);
		for (int i = 1; i < len; i++) {
			boolean match = false;
			for (Map.Entry<Integer, List<String>> entry : map.entrySet()) {
				int idx = entry.getKey().intValue();
				if (isSameArr(cntArr[i], cntArr[idx])) {
					entry.getValue().add(strs[i]);
					match = true;
					break;
				}
			}
			if (!match) {
				List<String> tmpList = new ArrayList<>();
				tmpList.add(strs[i]);
				map.put(i, tmpList);
			}
		}

		for (Map.Entry<Integer, List<String>> entry : map.entrySet()) {
			retList.add(entry.getValue());
		}

		return retList;
	}

	private boolean isSameArr(int[] arr1, int[] arr2) {
		for (int i = 0; i < 26; i++) {
			if (arr1[i] != arr2[i]) {
				return false;
			}
		}
		return true;
	}

}